package leetcode;

public class SingleNumber {

	public static void main(String[] args) {
		int[] array = { 499, 499, 499, 56, 56, 56, 24, 24, 24, 32, 5, 5, 32, 5,
				32, 4, 4, 4, 1, 3, 3, 3, 2, 2, 2 };
		int[] array1 = { 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1 };
		System.out.println(new SingleNumber().singleNumber(array));
		System.out.println(new SingleNumber().singleNumber(array1));
	}

	public int singleNumber(int[] A) {
		// discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions/1
		// 这里面有详解，这里主要说一下思想
		// 因为出现的是三次，所以需要设计成一个数出现3次之后自动会变为0，这就代表不影响后面的数
		// 现在只用bit来表示，a，b可能是0,1的组合，c(next bit)可能是0或者1
		// 采用两位a,b来表示. a ，b 的值可能为0 0 ，0 1 ，10
		// 分别代表0次，1次，2次。不可能出现1 1。因为3次之后就清0了
		// 当对应不同的数字时，无非就是把一位的情况扩展到了32位。但逻辑运算（对于每一位的仍然一样）
		int a = 0;
		int b = 0;
		int ta = 0;
		for (int c : A) {
			ta = (~a & b & c) | (a & ~b & ~c); // 这里之所以需要使用ta，是因为计算b的时候需要a的旧值
			b = (~a & ~b & c) | (~a & b & ~c);
			a = ta;
			System.out.println("a: " + a + "b: " + b);
		}
		// we need find the number that is 01,10 => 1, 00 => 0.
		// return a|b 意思是返回出现一次或者出现两次的那个数(假设不知道一个数是出现了一次还是两次)
		// 不管只有一个数出现了一次还是两次，另一个数一定为0；相或即可
		// 对于这道题，由于已经知道只会出现一次，返回b即可
		return a | b;
	}

	// 看不懂上面写的了
	// 谈一谈这道题的通解，所有的数都出现了K次，有一个数只出现了p次
	// 由于出现了k次，那么我们就需要数字来进行记录，2^m >= k即可
	// 如果不等于k的时候会出现一个问题，那就是怎样知道出现了k次并重新置0呢
	// 这就是需要掩码的原因，k的二进制表示中有m位，有为0的，也有不为0的，那怎样在确定出现k次的时候将所有的
	// x1...xm置为0呢，显然是与操作
	// 根据k的二进制，为1的就取xj，为0的取~xj，mask = ~(x1 & x2 & ~xj &...&
	// xm)(假设是这样的，根据k不同mask不同)
	// 当xj为0的时候，此时x1...xm组成的数恰好为k，mask为0(当且仅当)，所以应该置为0
	public int singleNumber2(int[] A) {
		int x1 = 0;
		int x2 = 0;
		int mask = 0;

		for (int i : A) {
			// xm是高位，x1是最低位，这是逐渐进位的过程
			// 假设i只为0、1，x2x1 假设为01，遇到1之后应该变为10，就意味着1出现了两次
			// 显然x1 ^ 1 = 0, x2加1是有条件的，必须x1 = 1，并且遇到了1
			// 所以应该是x2 ^ (x1 & 1);如果x1为0的话，就只将x1变为1
			// 整个过程实际是00、01、10、11...k的变化
			//从高位往低位计算
			x2 ^= x1 & i;
			x1 ^= i;
			mask = ~(x1 & x2);
			x2 &= mask;
			x1 &= mask;
		}

		//至于返回，k次的全部删除了，只剩下出现p次的了(p' = p % k),如果拍p大于k显然就取余就行
		//为了表述的方便，假设p < k
		//就看p的二进制形式，从左往右哪一位为1，就返回x几
		return x1; // p = 1, in binary form p = '01', then p1 = 1, so we should
					// return x1;
					// if p = 2, in binary form p = '10', then p2 = 1, so we
					// should return x2.
	}
}
